package string_question.leecode.test14;

/**
 * 方法三： 前缀树(三种方法的时间复杂度都差不多)
 * @author code_yc
 * @version 1.0
 * @date 2020/7/5 10:25
 */
public class Solution3 {

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        TrieTree tree = new TrieTree();
        for (String str : strs) {
            tree.add(str);
        }
        int n = strs.length;
        if (strs[0].length() == 0) {
            return "";
        } else {
            return tree.getPrefixLen(n, strs[0]);
        }
    }

    class Node {
        int path;   // 记录经过当前节点的字符串的个数
        int end;    // 记录以当前节点结尾的字符串的个数
        Node[] next; // next数组，存储下一个节点的位置

        public Node() {
            this.next = new Node[26];
        }
    }

    class TrieTree {
        Node head;

        public TrieTree() {
            this.head = new Node();
        }

        public void add(String s) {
            char[] chars = s.toCharArray();
            int index;
            Node temp = head;
            temp.path++;
            for (char c : chars) {
                index = c - 'a';
                if (temp.next[index] == null) {
                    temp.next[index] = new Node();
                }
                temp = temp.next[index];
                temp.path++;
            }
            temp.end++;
        }

        public String getPrefixLen(int n, String s) {
            StringBuilder ans = new StringBuilder();
            Node temp = head;
            char[] chars = s.toCharArray();
            int index = 0;
            for (char c : chars) {
                index = c - 'a';
                temp = temp.next[index];
                if (temp.path != n) {
                    return ans.toString();
                }
                ans.append(c);
            }
            return ans.toString();
        }
    }
}
